package algorithms.leaning.class11;

import common.util.MyUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * 请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。
 * 如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。
 * 给定一个输入参数N，代表纸条都从下边向上方连续对折N次。 请从上到下打印所有折痕的方向。
 * 例如:N=1时，打印: down N=2时，打印: down down up
 *
 * @author guichang
 * @date 2021/6/10
 */

@SuppressWarnings("all")
public class Code7_二叉树_纸张对折凹凸 {

    public static void main(String[] args) {
        List<String> list = printCrease(3); // [凹, 凹, 凸, 凹, 凹, 凸, 凸]
        MyUtil.print(list);
    }

    /**
     * 打印n此后的折痕
     *
     * @param n 次数
     * @return 折痕列表
     */
    public static List<String> printCrease(int n) {
        List<String> list = new ArrayList<>();
        // 从第一次折痕开始，凹折痕
        inPrintCrease(n, "凹", list);
        return list;
    }

    /**
     * 中序遍历打印折痕
     *
     * @param n      总层数，就是折的次数
     * @param crease 折痕
     * @param list   折痕列表
     */
    private static void inPrintCrease(int n, String crease, List<String> list) {
        // 超过最大折纸次数
        if (n < 1) {
            return;
        }
        inPrintCrease(n - 1, "凹", list);
        list.add(crease);
        inPrintCrease(n - 1, "凸", list);
    }
}